Thực đơn
Thuật toán tìm đường đi trong mê cung Thuật toán PledgeNếu mê cung có các tường rời nhau, đồng thời lối vào lối ra của mê cung nằm trên tường bao của mê cung, thì thuật toán bám tường vẫn có thể tìm được đường ra. Tuy nhiên, nếu điểm vào nằm bên trong mê cung và tách rời khỏi lối ra, thì bám theo tường sẽ chỉ có thể đi thành 1 vòng cục bộ và không tìm được lối ra. Đối với trường hợp này, thuật toán Pledge (được đặt theo tên của Jon Pledge ở Exeter) có thể giải quyết được vấn đề.[3]
Giải thuật Pledge được thiết kế để vượt qua vật cản, bằng cách chọn một hướng đi bất kỳ. Khi gặp vật cản, thì chuyển sang di chuyển bám theo tường dọc theo vật cản, kết hợp với đếm góc quay. Sau khi bám tường và quay mà trở về lại đúng hướng đi ban đầu đồng thời tổng góc đã quay bằng '0' (zero) thì tức là đã vượt qua khỏi vật cản, thì không cần bám tường nữa và tiếp tục di chuyển theo hướng ban đầu đã chọn.
Chỉ thoát khỏi bám theo tường khi thỏa mãn cả hai điều kiện: "hướng hiện tại trùng với hướng ban đầu" và "tổng số góc đã quay bằng '0'". Điều này là cần thiết để giúp di chuyển vòng qua vật cản phức tạp ví dụ như vật cản hình chữ "G" như trong hình. Ở vị trí +360o, robot có hướng di chuyển cùng hướng ban đầu, nếu bỏ bám tường bên phải mà tiếp tục di chuyển thẳng thì sẽ đi vào 1 vòng lặp mà không thoát ra được. Thay vào đó, nếu tiếp tục bám vào tường phải và thực hiện quay cho đến khi tổng góc quay là '0' thì sẽ thoát ra khỏi vật cản.
Thực đơn
Thuật toán tìm đường đi trong mê cung Thuật toán PledgeLiên quan
Thuật ngữ giải phẫu cử động Thuật toán Thuật ngữ anime và manga Thuật ngữ lý thuyết đồ thị Thuật ngữ thiên văn học Thuật chiêu hồn Thuật toán Dijkstra Thuật ngữ tin học Thuật ngữ ngữ âm học Thuật toán sắp xếpTài liệu tham khảo
WikiPedia: Thuật toán tìm đường đi trong mê cung http://books.google.com/books?id=m3QTSMYm5rkC&pg=P... http://www.mazeworks.com/mazegen/ http://www.youtube.com/watch?v=FkueaIT6RSU&NR=1 http://www.youtube.com/watch?v=jhL8uELbVIM http://www.youtube.com/watch?v=yqZDYcpCGAI http://www.astrolog.org/labyrnth/algrithm.htm#solv... http://www.cb.uu.se/~cris/blog/index.php/archives/... https://www.youtube.com/watch?v=IIBwiGrUgzc https://www.youtube.com/watch?v=k1tSK5V1pds